#include <iostream>
#include <cstdlib>
#include <vector>
#include <queue>
#include <unordered_map>

#ifndef _PRIORITY_QUEUE_H_
#define _PRIORITY_QUEUE_H_

template <typename Unique, typename Comparable> class PriorityQueue
{
public:
    struct DataBase
    {
        Unique key;
        Comparable data;
        DataBase(const Unique & _key, const Comparable & _data)
            : key{_key}, data{_data} {}
        DataBase(Unique && _key, Comparable && _data)
            : key{ std::move(_key) }, data{ std::move(_data) } {}
    };

private:
    struct HeapNode
    {
        DataBase value;
        int dist;
        HeapNode *left, *right, *father;
        HeapNode(const DataBase &_value)
            : value{_value} { dist = 0; left = right = father = nullptr; }
        HeapNode(DataBase && _value)
            : value{ std::move(_value) } { dist = 0; left = right = father = nullptr; }
    };
    HeapNode *root;
    static std::unordered_map<Unique, HeapNode*> heapNodeList;
    HeapNode * merge(HeapNode *p1, HeapNode *p2);
    void maintain(HeapNode *p);
    inline const int dist(HeapNode *p);

public:
    PriorityQueue() {root = nullptr;}
    bool empty();
    Comparable top();
    void clear();
    ~PriorityQueue() {clear();}
    void insert(const DataBase & x);
    void deleteMin();
    void buildHeap(const std::vector<DataBase> & input);
    void remove(const Unique &k);
    void modifyData(Unique k, Comparable d);
    void resetHash();
    void merge(PriorityQueue & H2);
};

//模板类中的静态成员变量需要在外部定义
template<typename Unique, typename Comparable>
std::unordered_map<Unique, typename PriorityQueue<Unique, Comparable>::HeapNode*> PriorityQueue<Unique, Comparable>::heapNodeList;

template<typename Unique, typename Comparable>
inline const int PriorityQueue<Unique, Comparable>::dist(HeapNode *p)
{
    return p == nullptr ? 0 : p->dist;
}

template<typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::maintain(HeapNode *p)
{
    if(dist(p->right) > dist(p->left))
        std::swap(p->left, p->right);
    p->dist = dist(p->right) + 1;
    if(p->left) p->left->father = p;
    if(p->right) p->right->father = p;
}

template<typename Unique, typename Comparable>
typename PriorityQueue<Unique, Comparable>::HeapNode * PriorityQueue<Unique, Comparable>::merge(HeapNode *p1, HeapNode *p2)
{
    if(p1 == nullptr) return p2;
    if(p2 == nullptr) return p1;
    if(p1->value.data > p2->value.data)
        std::swap(p1, p2);
    p1->right = merge(p1->right, p2);
    maintain(p1);
    return p1;
}

template<typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::insert(const DataBase & x)
{
    if(heapNodeList.count(x.key))
    {
        std::cerr << "Error! The key of Database is NOT UNIQUE!" << std::endl;
        exit(-1);
    }
    HeapNode *newnode = new HeapNode(x);
    heapNodeList[x.key] = newnode;
    root = merge(root, newnode);
}

template<typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::remove(const Unique &k)
{
    if(!heapNodeList.count(k))
    {
        std::cerr << "Error! Cannot find key in remove(const Unique &)!" << std::endl;
        exit(-1);
    }
    HeapNode *p = heapNodeList[k];
    if(p == root)
        return deleteMin();
    HeapNode *fa = p->father;
    if(p == fa->left)
        fa->left = merge(p->left, p->right);
    else
        fa->right = merge(p->left, p->right);
    maintain(fa);
    delete p;
    heapNodeList.erase(k);
}

template<typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::modifyData(Unique k, Comparable d)
{
    remove(k);
    insert(DataBase(k, d));
}

template<typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::deleteMin()
{
    if(root == nullptr)
    {
        std::cerr << "Error! Used deleteMin() in an empty PriorityQueue." << std::endl;
        exit(-1);
    }
    HeapNode *p = root;
    root = merge(root->left, root->right);
    if(root) root->father = nullptr;
    heapNodeList.erase(p->value.key);
    delete p;
}

template<typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::merge(PriorityQueue<Unique, Comparable> & H2)
{
    root = merge(root, H2.root);
    H2.root = nullptr;
}

template<typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::buildHeap(const std::vector<PriorityQueue<Unique, Comparable>::DataBase> & input)
{
    static std::queue<HeapNode*> nodes;
    for(const DataBase & x : input)
    {
        HeapNode *newnode = new HeapNode(x);
        heapNodeList[x.key] = newnode;
        nodes.push(newnode);
    }
    while(nodes.size() > 1)
    {
        HeapNode *p1 = nodes.front();
        nodes.pop();
        HeapNode *p2 = nodes.front();
        nodes.pop();
        nodes.push(merge(p1, p2));
    }
    root = nodes.front();
    nodes.pop();
}

template<typename Unique, typename Comparable>
bool PriorityQueue<Unique, Comparable>::empty()
{
    return root == nullptr;
}

template<typename Unique, typename Comparable>
Comparable PriorityQueue<Unique, Comparable>::top()
{
    if(root == nullptr)
    {
        std::cerr << "Error! Used top() in an empty PriorityQueue." << std::endl;
        exit(-1);
    }
    return root->value.data;
}

template<typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::resetHash()
{
    heapNodeList.clear();
}

template<typename Unique, typename Comparable>
void PriorityQueue<Unique, Comparable>::clear()
{
    static std::queue<HeapNode*> nodes;
    if(root == nullptr) return;
    nodes.push(root);
    while(!nodes.empty())
    {
        HeapNode* p = nodes.front();
        nodes.pop();
        if(p->left) nodes.push(p->left);
        if(p->right) nodes.push(p->right);
        heapNodeList.erase(p->value.key);
        delete p;
    }
    root = nullptr;
}

#endif